COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.skip to column 1
C00010 ENDMK
C⊗;
.skip to column 1
.double space
#. %3Introduction and new definition of circumscription%1

	(McCarthy 1980) introduces the circumscription method of
non-monotonic reasoning and gives motivation, some mathematical properties
and some examples of its application.  While the present paper is
logically self-contained, motivation may require some acquaintance with
the earlier paper.  In particular we don't repeat its arguments about the
importance of non-monotonic reasoning in AI.  Also its examples are
instructive.

	Here we give a more symmetric notion of
circumscription and applications to the formal expression of common
sense facts.  Our goal is to express these facts in a way that would
be suitable for inclusion in a general purpose database of common
sense facts.  We imagine this database to be used by AI programs
written after the initial preparation of the database.  It would
be best if the writers of these programs didn't have to
be familiar with how the common sense facts about particular
phenomena are expressed.
Thus
common sense knowledge must be represented in a way that is not
specific to a particular application.

	It turns out that many such common sense facts can be formalized
in a uniform way.  A single predicate ⊗ab, standing for "abnormal" is
circumscribed with certain other predicates and functions considered as
variables that can be constrained to achieve the circumscription subject
to the axioms.  So far this seems to cover the use of circumscription to
represent default rules.
On the other hand, it doesn't seem that circumscribing abnormality can
be used to cover many of the examples of (McCarthy 1980) in which we
want to limit a set to those objects that must be members.
#. A new version of circumscription.

.skip 1

%3Definition:%1 Let  %2A(P;Q)%1 be a formula of second order logic, where ⊗P and
⊗Q are the predicate symbols occurring free in ⊗A(P;Q).  Let
Let ⊗E(P;Q,x)  be a wff in which
⊗P, ⊗Q  and a tuple ⊗x of individual variables occur free.  The circumscription
of  ⊗E(P;Q,x)  relative to  ⊗A(P;Q)  is the formula  ⊗A'(P;Q)  defined by

!!a1:	%2A(P:Q) ∧ ∀P'.[A(P';Q) ∧ [∀x.E(P';Q,x) ⊃ E(P;Q,x)] ⊃ [∀x.E(P';Q,x) ≡ E(P;Q,x)]].%1

[We are here writing ⊗A(P;Q) instead of %2A(Pq1,...,Pqm;Qq1,...,qm)%1 for brevity
and likewise writing ⊗E(P;Q,x) instead of
%2E(Pq1,...,Pqm;Qq1,...,Qqm,xq1,...,xqm)%1.
Likewise the quantifier ⊗∀x stands for %2∀xq1...xqm%1.
In principle ⊗A(P;Q) may have embedded quantifiers, but we have no applications
yet that use this generality.  Circumscription is a kind of minimization,
and the predicate symbols ⊗Q act as parameters in this minimization.

.skip 1
	There are several differences between this and (McCarthy 1980).  First,
in that paper  ⊗E(P;Q,x)  had the specific form  ⊗P(x).  Here we speak of
circumscribing a wff, while there we could speak of circumscribing a predicate.
We can still speak of circumscribing the predicate ⊗P when ⊗E(P;Q,x) has
the special form ⊗P(x).  The present form is more symmetric in that
all of the predicate symbols in ⊗P are regarded as variables, and a wff
is minimized, whereas the earlier form distinguishes one of the predicates
themselves for minimization.  However, the present form is reducible to
the earlier form.

	Second, in ({eq a1}) we use an explicit quantifier for the predicate
variable  ⊗P' whereas in (McCarthy 1980), the formula was a schema.
One advantage of the present formalism is that now  ⊗A'(P)  is the
same kind of formula as ⊗A(P) and can be used as part of the axiom for
circumscribing some other wff.

Remark: The predicate symbols %2Pq1,...,Pqm%1 will not usually be all the
predicate symbols occurring in ⊗A(P). 
The situation is analogous to a minimization problem in calculus
or calculus of variations.  Some quantity is being minimized.  Other
quantities are variables whose values are to be chosen so as to achieve
the minimum.  Still others are parameters.  They are not varied
in the minimization process, and therefore the minimum obtained and the
values of the minimizing variables depend
on the values of the parameters.  We will point out the variables and
the parameters in the subsequent examples.

	In some of the literature, it has been supposed that non-monotonic
reasoning involves giving all predicates their minimum extension.  This
mistake has led to theorems about what reasoning cannot be
done that are irrelevant to AI and database theory,
because their premisses are too narrow.
.skip 2